Prior art functional approximation methods have fallen into three general categories: lookup table approaches, polynomial techniques like the Chebyshev Series, and an approach called the CORDIC approach or conversion transformations. Each approach suffers serious drawbacks with respect to the amount of computational resources required to implement them or the amount of time required to complete the implementation of the approach. The lookup table approach suffers from the requirement that a relatively large amount of hardware needs to be dedicated to the implementation of the approach to effectively exploit the inherent speed improvements found in the look up table approach. The Chebyshev approach is applicable for fixed and floating point arithmetic. However, the Chebyshev approach suffers from the need for high computational capabilities. High computational capabilities imply relatively large amounts of hardware or high clock speeds or both. This hardware requirement makes the Chebyshev approach generally over burdensome for fixed point arithmetic. Similarly, the CORDIC approach suffers time, complexity and space constraints. The CORDIC approach utilizes an iterative solution to the approximation problem that is hardware intensive.
Lookup table approaches depend on the accessing of a memory location for each argument to be approximated. Thus the resolution and accuracy of lookup table methods depend heavily on the amount of memory being dedicated. Thus a 4K byte memory having 8 bits per byte would be able to represent 4 thousand different arguments regardless of the type of argument addressing. Each resultant would contain at most 256 different values.
The Chebyshev polynomial evaluation method allows the approximation of vector-valued elementary functions for real time applications. A scale function evaluator using Chebyshev approximation consists of three components as described in a paper by Kai Hwang, H.C. Wang and Z. Xu entitled "Evaluating Elementary Functions With Chebyshev Polynomials On Pipeline Nets" in the IEEE Computer Society Proceedings of the 8th Symposium on Computer Arithmetic 1987, pp. 121-128 M.J. Irwin Ed. As explained in Hwang, et al the preprocessing unit preforms range reduction on the incoming data arguments; the Chebyshev approximator evaluates the truncated Chebyshev series and the postprocessing unit restores the function values with respect to the original arguments. The preprocessing and postprocessing tasks are complementary and closely interrelated. They are also function dependent.
The Coordinate Rotational Digital Computer(CORDIC) is a special-purpose digital computer for real-time airborne computation. The computer was developed for the solution of trigonometric relations involved in plane coordinate rotation and conversion from rectangular to polar coordinates. The CORDIC computer consisted of three shift registers, three adder-subtractors, and special interconnections. The CORDIC computing technique was developed especially for use in real-time digital computing environments involving discontinuous, programmed solutions of trigonometric relationships.
The CORDIC approach implemented the digital equivalent of an analog resolver. Computation is divided between a rotation mode and vectoring mode. In the rotation mode the coordinate components of the original vector after rotation through a given angle, is computed. In vectoring mode the coordinate components of the vector are given and the magnitude and angular argument of the original vector are computed. In vectoring mode, rotation and feedback are utilized. The original coordinates are rotated until the angular argument is zero. In the CORDIC approach the basic computing technique is a step-by-step sequence of pseudo rotations which result in an over-all rotation through a given angle or result in a final angular argument of zero. A good description of the CORDIC computing method can be found in an article by Jack E. Volder entitled "The CORDIC Trigonometric Computing Technique", IRE Transactions on Electronic Computing EC-8: pages 330-334 (1959).
It is therefore the motivation of the invention to provide a transcendental function approximation technique that reduces the amount of memory and computational hardware needed to approximate a transcendental function without compromising the speed or accuracy of the approximation.